{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><font size=6> LightGBM </font></center>\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#简介\" data-toc-modified-id=\"简介-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>简介</a></span></li><li><span><a href=\"#LightGBM的特性\" data-toc-modified-id=\"LightGBM的特性-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>LightGBM的特性</a></span><ul class=\"toc-item\"><li><span><a href=\"#在速度&amp;内存方面的优化\" data-toc-modified-id=\"在速度&amp;内存方面的优化-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>在速度&amp;内存方面的优化</a></span><ul class=\"toc-item\"><li><span><a href=\"#减少计算每次分裂时的gain\" data-toc-modified-id=\"减少计算每次分裂时的gain-2.1.1\"><span class=\"toc-item-num\">2.1.1&nbsp;&nbsp;</span>减少计算每次分裂时的gain</a></span></li><li><span><a href=\"#使用直方图减法进行进一步加速分裂过程\" data-toc-modified-id=\"使用直方图减法进行进一步加速分裂过程-2.1.2\"><span class=\"toc-item-num\">2.1.2&nbsp;&nbsp;</span>使用直方图减法进行进一步加速分裂过程</a></span></li><li><span><a href=\"#降低内存的使用\" data-toc-modified-id=\"降低内存的使用-2.1.3\"><span class=\"toc-item-num\">2.1.3&nbsp;&nbsp;</span>降低内存的使用</a></span></li><li><span><a href=\"#减少并行学习的通信代价\" data-toc-modified-id=\"减少并行学习的通信代价-2.1.4\"><span class=\"toc-item-num\">2.1.4&nbsp;&nbsp;</span>减少并行学习的通信代价</a></span></li><li><span><a href=\"#稀疏数据优化\" data-toc-modified-id=\"稀疏数据优化-2.1.5\"><span class=\"toc-item-num\">2.1.5&nbsp;&nbsp;</span>稀疏数据优化</a></span></li></ul></li><li><span><a href=\"#LightGBM在精度方面的优化\" data-toc-modified-id=\"LightGBM在精度方面的优化-2.2\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>LightGBM在精度方面的优化</a></span><ul class=\"toc-item\"><li><span><a href=\"#树的生成方式\" data-toc-modified-id=\"树的生成方式-2.2.1\"><span class=\"toc-item-num\">2.2.1&nbsp;&nbsp;</span>树的生成方式</a></span><ul class=\"toc-item\"><li><span><a href=\"#传统的树增长的方式(Level(Depth)-wise)\" data-toc-modified-id=\"传统的树增长的方式(Level(Depth)-wise)-2.2.1.1\"><span class=\"toc-item-num\">2.2.1.1&nbsp;&nbsp;</span>传统的树增长的方式(Level(Depth)-wise)</a></span></li><li><span><a href=\"#LightGBM增长的方式(Leaf-wise)\" data-toc-modified-id=\"LightGBM增长的方式(Leaf-wise)-2.2.1.2\"><span class=\"toc-item-num\">2.2.1.2&nbsp;&nbsp;</span>LightGBM增长的方式(Leaf-wise)</a></span></li></ul></li><li><span><a href=\"#类别(Categorical)特征的最优分割\" data-toc-modified-id=\"类别(Categorical)特征的最优分割-2.2.2\"><span class=\"toc-item-num\">2.2.2&nbsp;&nbsp;</span>类别(Categorical)特征的最优分割</a></span></li></ul></li><li><span><a href=\"#并行学习层面的优化\" data-toc-modified-id=\"并行学习层面的优化-2.3\"><span class=\"toc-item-num\">2.3&nbsp;&nbsp;</span>并行学习层面的优化</a></span><ul class=\"toc-item\"><li><span><a href=\"#特征并行\" data-toc-modified-id=\"特征并行-2.3.1\"><span class=\"toc-item-num\">2.3.1&nbsp;&nbsp;</span>特征并行</a></span><ul class=\"toc-item\"><li><span><a href=\"#传统的算法\" data-toc-modified-id=\"传统的算法-2.3.1.1\"><span class=\"toc-item-num\">2.3.1.1&nbsp;&nbsp;</span>传统的算法</a></span></li><li><span><a href=\"#LightGBM中的特征并行\" data-toc-modified-id=\"LightGBM中的特征并行-2.3.1.2\"><span class=\"toc-item-num\">2.3.1.2&nbsp;&nbsp;</span>LightGBM中的特征并行</a></span></li></ul></li><li><span><a href=\"#数据并行\" data-toc-modified-id=\"数据并行-2.3.2\"><span class=\"toc-item-num\">2.3.2&nbsp;&nbsp;</span>数据并行</a></span><ul class=\"toc-item\"><li><span><a href=\"#传统的算法\" data-toc-modified-id=\"传统的算法-2.3.2.1\"><span class=\"toc-item-num\">2.3.2.1&nbsp;&nbsp;</span>传统的算法</a></span></li><li><span><a href=\"#LightGBM中的数据并行\" data-toc-modified-id=\"LightGBM中的数据并行-2.3.2.2\"><span class=\"toc-item-num\">2.3.2.2&nbsp;&nbsp;</span>LightGBM中的数据并行</a></span></li></ul></li><li><span><a href=\"#Voting-Parallel\" data-toc-modified-id=\"Voting-Parallel-2.3.3\"><span class=\"toc-item-num\">2.3.3&nbsp;&nbsp;</span>Voting Parallel</a></span></li></ul></li><li><span><a href=\"#其他优化\" data-toc-modified-id=\"其他优化-2.4\"><span class=\"toc-item-num\">2.4&nbsp;&nbsp;</span>其他优化</a></span></li></ul></li><li><span><a href=\"#小结\" data-toc-modified-id=\"小结-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>小结</a></span></li><li><span><a href=\"#参考文献\" data-toc-modified-id=\"参考文献-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>参考文献</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 简介\n",
    "\n",
    "之前我们介绍了XGBoost的原理,XGBoost是数据竞赛圈非常棒的工具,但是后来随着数据的不断增大,对于模型内存以及运行速度的要求越来越高,XGBoost在很多数据竞赛或者工程任务中已经较难满足大家的需求，后来随着微软LightGBM的出现,并因其在内存控制以及速度方面的优势,大家也渐渐转向了LightGBM.\n",
    "\n",
    "在这两年的时间中,LightGBM也在诸多数据竞赛任务中取得了不错的成绩。如下表所示,摘自<font color=blue>[8]</font>：\n",
    "  \n",
    "\n",
    "| Place         | Competition   | Solution  | Date |\n",
    "| ------------- |:------------- | --------- | -----|\n",
    "| 1st     | [TalkingData AdTracking Fraud Detection Challenge](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection) | [link](https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56475)| 2018.5 |\n",
    "| 1st     | [DonorsChoose.org Application Screening](https://www.kaggle.com/c/donorschoose-application-screening)| [link](https://www.kaggle.com/shadowwarrior/1st-place-solution/notebook) | 2018.4 | \n",
    "| 1st     | [Toxic Comment Classification Challenge](https://www.kaggle.com/c/jigsaw-toxic-comment-classification-challenge)| [link](https://www.kaggle.com/c/jigsaw-toxic-comment-classification-challenge/discussion/52557) | 2018.3 |\n",
    "| 1st     | [Mercari Price Suggestion Challenge](https://www.kaggle.com/c/mercari-price-suggestion-challenge) | [link](https://www.kaggle.com/c/mercari-price-suggestion-challenge/discussion/50256) | 2018.2 |\n",
    "| 1st     | [IEEE's Signal Processing Society, Camera Model Identification](https://www.kaggle.com/c/sp-society-camera-model-identification)| [link](https://www.kaggle.com/c/sp-society-camera-model-identification/discussion/49367) | 2018.2 | \n",
    "| 1st     | [Recruit Restaurant Visitor Forecasting](https://www.kaggle.com/c/recruit-restaurant-visitor-forecasting) | [link](https://www.kaggle.com/pureheart/1st-place-lgb-model-public-0-470-private-0-502/comments) | 2018.2| \n",
    "| 1st     | [WSDM CUP 2018 - KKBox's Music Recommendation Challenge](https://www.kaggle.com/c/kkbox-music-recommendation-challenge) | [link](https://www.kaggle.com/c/kkbox-music-recommendation-challenge/discussion/45942) | 2017.12 |\n",
    "| 1st     | [Porto Seguro’s Safe Driver Prediction](https://www.kaggle.com/c/porto-seguro-safe-driver-prediction) | [link](https://www.kaggle.com/c/porto-seguro-safe-driver-prediction/discussion/44629) |2017.11 |\n",
    "| 1st     | [Quora Question Pairs](https://www.kaggle.com/c/quora-question-pairs) | [link](https://www.kaggle.com/c/quora-question-pairs/discussion/34355) | 2017.6 |\n",
    "| 1st     | [Two Sigma Connect: Rental Listing Inquiries](https://www.kaggle.com/c/two-sigma-connect-rental-listing-inquiries) | [link](https://www.kaggle.com/c/two-sigma-connect-rental-listing-inquiries/discussion/32163) | 2017.4 |\n",
    "| 1st     | [CIKM2017 AnalytiCup - Lazada Product Title Quality Challenge](http://cikm2017.org/CIKM_AnalytiCup_task3.html) | [link](http://cikm2017.org/download/analytiCup/session3/CIKMAnalytiCup2017_LazadaProductTitleQuality_T3.pdf) | 2017.9 |\n",
    "| 2nd     | [Two Sigma Connect: Rental Listing Inquiries](https://www.kaggle.com/c/two-sigma-connect-rental-listing-inquiries) | [link](https://www.kaggle.com/c/two-sigma-connect-rental-listing-inquiries/discussion/32148) | 2017.4 |\n",
    "| 3rd     | [Two Sigma Connect: Rental Listing Inquiries](https://www.kaggle.com/c/two-sigma-connect-rental-listing-inquiries) | [link](https://www.kaggle.com/c/two-sigma-connect-rental-listing-inquiries/discussion/32123) | 2017.4 |\n",
    "| 3rd     | [Dogs vs. Cats Redux: Kernels Edition](https://www.kaggle.com/c/dogs-vs-cats-redux-kernels-edition) | [link](http://blog.kaggle.com/2017/04/20/dogs-vs-cats-redux-playground-competition-3rd-place-interview-marco-lugo) | - |\n",
    "| 3rd     | [Bosch Production Line Performance](https://www.kaggle.com/c/bosch-production-line-performance) | [link](http://blog.kaggle.com/2016/12/15/bosch-production-line-performance-competition-winners-interview-3rd-place-team-data-property-avengers-darragh-marios-mathias-stanislav) | 2016.11 |\n",
    "| 1st     | [The 1st Di-Tech Competitions](http://research.xiaojukeji.com/competition/main.action?competitionId=DiTech2016) | - | 2016.7 |\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因为LightGBM每次分裂的loss计算和XGBoost是一样的,所以此处不再累述相应的数学公式,有兴趣的可以参考之前我写的XGBoost部分,此处我们主要介绍:\n",
    "\n",
    "1. LightGBM与之前GBDT模型在树学习部分的区别,主要是树的生成方式以及histogram的技巧等;\n",
    "2. LightGBM在算法层面以及并行优化方面的改进;(数据层面的优化,特征层面的优化)\n",
    "3. LightGBM在其他方面的优化,主要是NIPS17年提到的GOSS算法以及EFB算法;\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LightGBM的特性\n",
    "\n",
    "LightGBM中的优化的方式和XGBoost是类似的,都是在每个节点处寻找最小化loss的分割点,所以此处我们重点介绍LightGBM相较于其他类似算法的不同之处以及其优点。\n",
    "\n",
    "## 在速度&内存方面的优化\n",
    "\n",
    "许多boosting的工具会使用预先排序算法来加速决策树的学习(例如XGB),这是一个很简单的方法,但是却难以优化,那么LightGBM如何来加速呢?\n",
    "\n",
    "LightGBM采用基于直方图的方法,这样我们就可以将连续的值转化为离散的bins,这样可以带来的好处是:\n",
    "\n",
    "### 减少计算每次分裂时的gain\n",
    "\n",
    "- 预先排序的算法需要处理的时间复杂度是和样本的个数相关的, 即它的时间复杂度为O(# data);\n",
    "- 当我们将连续值转化为直方图时,转化的过程的时间复杂度和O(# data)相关,前期会耗一些时间,但是一旦转化完成,基于直方图的算法的时间复杂度将会和 O(# bins)相关, 其中#bins会小于# data\n",
    "\n",
    "### 使用直方图减法进行进一步加速分裂过程\n",
    "\n",
    "- 为了获取二分树的叶子的直方图,我们只需要计算它的父亲以及其邻居的减法\n",
    "\n",
    "![](./pic/histogram_split_speedup.png)\n",
    "\n",
    "- 所以我们只需要构建一个叶子的直方图(带有比其邻居少的数据), 然后便可以以O(#bins)的代价获得它的邻居的直方图;\n",
    "\n",
    "\n",
    "### 降低内存的使用\n",
    "- 因为我们将连续值以离散的bins替换了,如果#bins较少的话,我们便可以对其进行数据格式的转换,例如转换为uint8等等来存储训练数据;\n",
    "- 我们无需存储预先排序特征的额外信息;\n",
    "\n",
    "### 减少并行学习的通信代价\n",
    "- 部分细节可以参考后面的内容.\n",
    "\n",
    "### 稀疏数据优化\n",
    "\n",
    "- 对于稀疏形式的数据,我们仅需要O(2 * #non_zero_data)的时间复杂度来对稀疏的特征进行直方图的构建\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LightGBM在精度方面的优化\n",
    "\n",
    "### 树的生成方式\n",
    "\n",
    "#### 传统的树增长的方式(Level(Depth)-wise)\n",
    "\n",
    "![](./pic/level_wise.png)\n",
    "\n",
    "上面的图展示了level-wise的生成过程,我们可以很容易发现这种生成方式的问题,如下图:\n",
    "\n",
    "\n",
    "![](./pic/level_wise_bad.png)\n",
    "\n",
    "我们发现对1进行分裂可以带来更大的收益,但是在level-wise的过程中,我们可能还是会先对2进行分裂,然后在下一层再考虑是否对1进行分裂,所以这是一种不太合理的形式。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "#### LightGBM增长的方式(Leaf-wise)\n",
    "\n",
    "![](./pic/leaf-wise.png)\n",
    "\n",
    "LightGBM采用更加贪心的方式,从而解决上面我们所说的问题,但是我们也可以很容易发现,这样的方式很容易过拟合,而且很容易导致我们的树的深度出现很深的情况从而导致模型过拟合,为了防止过拟合,大家在模型调参的时候需要好好考虑参数<font color=red>num_leaves 以及 max_depth </font>, \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 类别(Categorical)特征的最优分割\n",
    "\n",
    "我们发现在数据竞赛或者工程项目中常常不可避免的会碰到类别特征,类别特征的处理往往对于模型的影响非常大,尤其是针对那些无序的类别特征,例如颜色,商铺类型等特征。\n",
    "\n",
    "针对类别特征最简单的处理方式是one-hot展开,<font color=red>这种方式很多时候效果是不佳的,除非该列特征很冗余,例如1000个类别里面有10个是核心类,其他类都是噪音这种,one-hot展开往往能取得不错的效果,具体的案例可以参考DC的讯飞推荐比赛</font><font color=blue>[8]</font>。 其余时候one-hot的方式往往导致树的搜索深度大大增加而只能取得次优的效果。\n",
    "\n",
    "理论上对类别特征进行 最优的分割方式是对类别特征进行枚举组合,例如对于某个类别特征,它一共有$k$个不同的值,对其进行分类我们一共可以得到$2^{k-1} - 1$个组合,通过计算每个组合可以带来的收益,我们取收益最大的点进行分裂,但是我们也发现这样的方式计算代价是巨大的。不过对于回归树或者二分类问题,有一种方法只需要O(k * log(k))的时间复杂度即可寻找到最优分裂点,该算法的大致思想是：\n",
    "\n",
    "在每次分裂时,我们按照训练目标对每个类进行排序,对应到LightGBM中,我们根据累计值<font color=red>(sum  gradient / sum hessian)</font><font color=blue>[1]</font>.进行排序,然后按照排序后的直方图寻找最佳分裂点。具体的细节可以参考<font color=blue>[2]</font>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 并行学习层面的优化\n",
    "\n",
    "**LightGBM和XGBoost在每棵树的学习本质上并没有质的变化(树每次分割的计算指标是一样的),但是LightGBM在内存控制以及速度方面却比XGBoost好了很多**,这里我们看一下LightGBM在并行学习方面做了哪些工作。\n",
    "\n",
    "### 特征并行\n",
    "\n",
    "特征并行的目标在于更快的寻找到每个特征的最佳分割点,传统的做法是:\n",
    "\n",
    "#### 传统的算法\n",
    "\n",
    "1. 将数据进行垂直分割(即特征分割),不同的机器拥有不同的特征列;\n",
    "2. 每个worker在局部特征集合上计算局部最优分裂点,（feature, threshold）;\n",
    "3. 所有workder进行通信并且获得最佳的分裂点;\n",
    "4. 我们在最佳的分割点上进行分割,然后将数据分割之后的结果通讯到其他的worker上面;\n",
    "5. 所有其他的worker根据接受到的数据再对数据进行分割;\n",
    "\n",
    "![](./pic/traditional_feature_split.png)\n",
    "\n",
    "\n",
    "**传统算法的缺点**:\n",
    "\n",
    "- 会有较大的计算开销,因为这样没法加速分裂的速度,每个特征列计算分裂点的时间复杂度为O(#data), 所以当数据的个数较多的时候,我们并无法加速太多;\n",
    "\n",
    "- 每次分裂完成都需要进行communication,这样的代价在需要分裂较多的时候还是很大的, 大概需要O(#data / 8)的代价( 一个数据一位,one bit for one data ).\n",
    "\n",
    "#### LightGBM中的特征并行\n",
    "\n",
    "因为在数据很大的时候特征的并行并无法带来太多的加速,所以我们对数据不再进行分割,而是每个worker都保留所有的数据,这样worker之间就无需再进行任何通信,因为每个worker都已经知道了最佳的分裂点，所以当#data 并非那么大的时候,我们的机器其实是可以存下所有的数据的。\n",
    "\n",
    "1. Workers在本地的特征集合上面找到每个特征列的最佳分裂点(每个worker还是查找不同特征子集的分裂点);\n",
    "2. 对所有的特征列的最佳分裂点进行通信并找出最好的那一个;\n",
    "3. 进行最优的分裂(因为本地保留了所有的数据,所以无需再进行通讯);\n",
    "\n",
    "但是从上面的算法看来,**这种特征并行的方式在#data很大的时候仍然需要大量的计算开销,所以我们当数据较大的时候,需要对数据进行并行化.**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 数据并行\n",
    "\n",
    "特征并行部分我们通过在每个worker上保留所有数据同时每个worker只处理某个特征子集的方式减少了广播instance indices的代价,但是我们也发现这样带来的一个问题就是当数据量特别大的时候,每个worker的存储代价是非常巨大的,此时我们需要将数据分开处理。\n",
    "\n",
    "#### 传统的算法\n",
    "\n",
    "1. 我们将数据进行水平划分;(即对样本进行划分)\n",
    "2. 每个worker对本地的数据进行直方图的构建;\n",
    "3. 将所有局部的直方图进行Merge;\n",
    "4. 从merged的全局直方图中寻找最佳分类点,然后开始进行分裂操作. \n",
    "\n",
    "![](./pic/traditional_data_split.png)\n",
    "\n",
    "**传统算法的缺点**:\n",
    "- 有高昂的通讯代价,如果使用点到点的通讯算法,那么每台机器的通讯代价是O(#machine * #feature * #bin);如果使用集体通讯(ALL Reduce),那么通讯代价是 O(2 \\* #feature \\* #bin).\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### LightGBM中的数据并行\n",
    "1. LightGBM采用Reduce Scatter对不同的worker的不同特征的直方图进行合并,然后workers在本地merged的直方图上找到最佳分割点，并同步寻找全局最佳分割点;\n",
    "2. 前面有提到,LightGBM使用直方图减法来加速训练,这样的话,我们只需要计算一个叶子的直方图就能同时获得到其邻居的直方图;\n",
    "\n",
    "数据并行在LightGBM中的时间复杂度为O(0.5 \\* #feature \\*#bin)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Voting Parallel\n",
    "\n",
    "Voting parallel可以进一步将数据并行的通讯代价降至常熟代价,它可以进一步减少特征直方图通讯之间的代价,具体的可细节大家以参考论文.<font color=blue>[9]</font>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 其他优化 \n",
    "\n",
    "具体的细节大家可以参考论文<font color=blue>[5]</font>\n",
    "\n",
    " Gradient-based One Side Sampling (GOSS) 和 Exclusive Feature Bundling (EFB)。在不影响精度的情况下，两个算法分别减少了GBDT训练中所需的数据量和特征量，从而加速了GBDT的训练。 \n",
    " \n",
    "- GOSS算法: 在每一次迭代前，利用了GBDT中的样本梯度和误差的关系，对训练样本进行采样: 对误差大（梯度绝对值大）的数据保留；对误差小的数据采样一个子集，但给这个子集的数据一个权重，让这个子集可以近似到误差小的数据的全集。这么采样出来的数据，既不损失误差大的样本，又在减少训练数据的同时不改变数据的分布，从而实现了在几乎不影响精度的情况下加速了训练。\n",
    "<br /> \n",
    "- EFB算法：在特征维度很大的数据上，特征空间一般是稀疏的。利用这个特性，我们可以无损地降低GBDT算法中需要遍历的特征数量，更确切地说，是降低构造特征直方图（训练GBDT的主要时间消耗）需要遍历的特征数量。在稀疏的特征空间中，很多特征是exclusive的（即在同一个样本里，这一组特征里最多只有一个特征不为0）。每一组exclusive feature都可以无损地合并成一个“大特征”。构造直方图的时候，遍历一个“大特征”可以得到一组exclusive feature的直方图。这样只需要遍历这些“大特征”就可以获取到所有特征的直方图，降低了需要遍历的特征量。这里还需要解决的是Exclusive feature的分组问题，这是一个NP问题，可以转成Graph Coloring (Graph coloring - Wikipedia) 问题，并用贪心的近似方法来求解。结合这两个算法，LightGBM在一些大数据集上（kdd2010, kdd2012）可以实现20倍左右的加速效果，并且不损失精度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 小结\n",
    "\n",
    "本篇notebook中,我们介绍了LightGBM的很多特性,包括树的生成方式(Leaf-Wise),处理连续特征所采用的直方图方法来降低内存,处理类别特征时所采用的快速对直方图排序寻找最优点的方式等; 还有在算法并行层面的加速,包括特征并行以及样本并行两块; 此外,LightGBM还有一些其他的优化方式,具体的细节大家可以参考论文<font color=blue>[5,9]</font>.\n",
    "\n",
    "了解了LightGBM和XGBoost的区别之后,大家就可以上手玩玩LightGBM工具包了,至于如何入手,大家可以参考LightGBM的工具包<font color=blue>[10]</font>.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 参考文献\n",
    "1. XGBoost原理：https://github.com/dayeren/Kaggle_Competition_Treasure/blob/master/Models/XGBoost/XGBoost_%E5%8E%9F%E7%90%86%E8%AE%B2%E8%A7%A3.ipynb\n",
    "2. Walter D. Fisher. \"On Grouping for Maximum Homogeneity.\" Journal of the American Statistical Association. Vol. 53, No. 284 (Dec., 1958), pp. 789-798.\n",
    "3. GBDT: http://wepon.me/files/gbdt.pdf\n",
    "4. https://www.zhihu.com/question/64943934/answer/226781510\n",
    "5. Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu. \"LightGBM: A Highly Efficient Gradient Boosting Decision Tree.\" Advances in Neural Information Processing Systems 30 (NIPS 2017), pp. 3149-3157.\n",
    "6. https://github.com/Microsoft/LightGBM/blob/master/docs/Features.rst\n",
    "7. https://github.com/Microsoft/LightGBM/blob/master/examples/README.md#machine-learning-challenge-winning-solutions\n",
    "8. 2018科大讯飞AI营销算法大赛: http://www.dcjingsai.com/common/cmpt/2018%E7%A7%91%E5%A4%A7%E8%AE%AF%E9%A3%9EAI%E8%90%A5%E9%94%80%E7%AE%97%E6%B3%95%E5%A4%A7%E8%B5%9B_%E7%AB%9E%E8%B5%9B%E4%BF%A1%E6%81%AF.html?slxydc=380dfb\n",
    "9. Qi Meng, Guolin Ke, Taifeng Wang, Wei Chen, Qiwei Ye, Zhi-Ming Ma, Tie-Yan Liu. \"A Communication-Efficient Parallel Algorithm for Decision Tree.\" Advances in Neural Information Processing Systems 29 (NIPS 2016), pp. 1279-1287.\n",
    "10. LightGBM Document:https://lightgbm.readthedocs.io/en/latest/"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
